package main

import "fmt"

type NumArray struct {
	value  []struct{  //线段树数组结构
		sum	  int	  //每个节点的求和
		lazy  int	  //懒标记
	}
	length int        //原数组的长度
}

//建树，线段树 树根的下标为1
func Constructor(nums []int) NumArray {
	tree := NumArray{make([]struct{sum, lazy int}, len(nums)<<2), len(nums)-1}   //为线段树开辟4倍空间
	tree.buildTree(nums, 1, 0, tree.length)
	return tree
}

//更新区间节点 区间里节点都加上val
func (this *NumArray) Update(L, R, val int) {
	this.update(1, 0, this.length, L, R, val)
}

//查找区间和
func (this *NumArray) SumRange(L, R int) int {
	return this.querySum(1, 0, this.length, L, R)
}

//根据nums数组构建线段树, treeIndex为线段树数组的当前下标，[left, right]为当前节点包含的区间
func (this *NumArray) buildTree(nums []int, treeIndex, left, right int) {
	// 递归终止条件, 当left 和 right 重合 就是叶子节点
	if left == right {
		this.value[treeIndex].sum = nums[left]   //叶子节点直接赋值
		return
	}
	mid := (left + right) >> 1          //一分为二
	treeLeft  := treeIndex << 1     	//线段树当前节点的左孩子(n*2 + 1)
	treeRight := treeIndex << 1 | 1     //线段树当前节点的右孩子(n*2 + 2)
	this.buildTree(nums, treeLeft, left, mid)             //递归左子树
	this.buildTree(nums, treeRight, mid+1, right)         //递归右子树
	//后序遍历, 更新当前节点的值为左右子树的和
	this.value[treeIndex].sum = this.value[treeLeft].sum + this.value[treeRight].sum
}

// [L,R] 为修改区间, val为被修改元素的变化量, [left, right] 为当前节点包含的区间, treeIndex 为当前节点的下标
func (this *NumArray) update(treeIndex, left, right, L, R, val int) {
	if L <= left && R >= right {	//找到或者包含区间[L, R]中的节点  [L--> [left, right]--> R]
		this.value[treeIndex].sum  = val * (right - left + 1)	//更新当前节点的值, val * 前节点包含的区间的个数
		this.value[treeIndex].lazy = val  // 打上懒标记
		return
	}
	mid := (left + right) >> 1
	treeLeft  := treeIndex << 1
	treeRight := treeIndex << 1 | 1
	//--->BEGIN 这里就是PushDown的内容,   懒标记下发
	if this.value[treeIndex].lazy != 0 {   //如果当前节点被打上了懒标记, 就把懒标记下发给下一层子节点
		//更新左子树节点sum的值 = 当前节点懒标记的值 * 左子树节点包含的区间的个数, 右子树同理
		this.value[treeLeft].sum  = this.value[treeIndex].lazy * (mid - left +1)
		this.value[treeRight].sum = this.value[treeIndex].lazy * (right - mid)
		//把当前节点的懒标记值, 更新到左右子树的节点, 并把当前节点的懒标记清空
		this.value[treeLeft].lazy  = this.value[treeIndex].lazy
		this.value[treeRight].lazy = this.value[treeIndex].lazy
		this.value[treeIndex].lazy = 0
	}
	//--->END
	if L <= mid {     //左区间有交集, 则更新左区间
		this.update(treeLeft, left, mid, L, R, val)
	}
	if R > mid {      //右区间有交集, 则更新右区间
		this.update(treeRight, mid+1, right, L, R, val)
	}
	//上推, 更新当前节点的值为左右子树的新和
	this.value[treeIndex].sum = this.value[treeLeft].sum + this.value[treeRight].sum
}

func (this *NumArray) querySum (treeIndex, left, right, L, R int) (ans int) {
	fmt.Printf("L=%d  R=%d sum=%d mark=%d\n", left, right, this.value[treeIndex].sum, this.value[treeIndex].lazy)
	//当[left, right] 在查询的区间[L, R]内 直接返回当前节点的值
	if L <= left && R >= right {
		return this.value[treeIndex].sum
	}
	mid := (left + right) >> 1
	treeLeft  := treeIndex << 1
	treeRight := treeIndex << 1 | 1
	//--->BEGIN 这里就是PushDown的内容,   懒标记下发
	if this.value[treeIndex].lazy != 0 { //如果当前节点被打上了懒标记, 就把懒标记下发给下一层子节点, 更新下一层的节点值
		this.value[treeLeft].sum   = this.value[treeIndex].lazy * (mid - left + 1)
		this.value[treeRight].sum  = this.value[treeIndex].lazy * (right - mid)
		this.value[treeLeft].lazy  = this.value[treeIndex].lazy
		this.value[treeRight].lazy = this.value[treeIndex].lazy
		this.value[treeIndex].lazy = 0
	}
	//--->END
	if mid >= L {
		ans += this.querySum(treeLeft, left, mid, L, R)
	}
	if R > mid {
		ans += this.querySum(treeRight, mid+1, right, L, R)
	}
	return
}

func main() {
	arr := []int{1, 3, 5,7,1,11}
	MyTree := Constructor(arr)
	MyTree.Update(4,4, 6)
	fmt.Println(MyTree.SumRange(2,5))
}
